package leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * 删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
 * <p>
 * 说明: 输入可能包含了除 ( 和 ) 以外的字符。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "()())()"
 * 输出: ["()()()", "(())()"]
 * 示例 2:
 * <p>
 * 输入: "(a)())()"
 * 输出: ["(a)()()", "(a())()"]
 * 示例 3:
 * <p>
 * 输入: ")("
 * 输出: [""]
 * <p>
 * <p>
 * <p>
 * 其他括号问题见
 * {@link leetcode.a_总结分布.Code03_括号问题}
 *
 * @date 2020/5/3 18:10
 */
public class Code301_DeleteInvalid_删除无效括号 {
    public static void main(String[] args) {
        String s = "(()";
        System.out.println(removeInvalidParentheses(s));
    }


    /**
     * 思路：先判断多余的(和)个数。
     * 然后利用递归，删除(或)。
     * 递归基是把这些多余的都删除了。
     *
     * @param s
     * @return
     */
    public static List<String> removeInvalidParentheses(String s) {
        List<String> res = new LinkedList<>();
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else if (s.charAt(i) == ')') {
                if (left > 0) left--;
                else right++;
            }
        }
        process(s, 0, left, right, res);
        if (res.size() == 0) res.add("");
        return res;
    }

    private static void process(String s, int index, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            check(s, res);
            return;
        }
        //连续的((( 或者)))只能删除一个
        for (int i = index; i < s.length(); i++) {
            // 如果不加这个条件，(()  会输出两组()()
            if (i != index && s.charAt(i) == s.charAt(i - 1)) continue;
            //不连续
            if (s.charAt(i) == '(' || s.charAt(i) == ')') {
                //删除第i个元素
                String cur = s.substring(0, i) + s.substring(i + 1);
                if (left > 0) {
                    //注意这里传入的下一个是i,因为当前被删除的是i，相当于i+1顶替了i的位置
                    process(cur, i, left - 1, right, res);
                } else if (right > 0) {
                    process(cur, i, left, right - 1, res);
                }
            }
        }

    }

    private static void check(String s, List<String> res) {
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                balance++;
            } else if (s.charAt(i) == ')') {
                if (balance <= 0) return;
                balance--;
            }
        }
        if (balance == 0) res.add(s);
    }


}
